Genetic Algorithm

Genetic algorithm use evolution to get close to a solution. At first we create a random set of solutions. Then we select the best solutions and use them to create new solutions. We repeat this process until we get a solution that is good enough. The process is similar to natural selection. The best solutions are selected to create new solutions. The new solutions are better than the old ones. The process is repeated until we get a solution that is good enough.

Fitness functions are used to evaluate the solutions. In this instance the algorithm makes use of elitism and mutation. Elitism is the process of selecting the best solutions and using them to create new solutions. Mutation is the process of randomly changing the solutions. This is done to prevent the algorithm from getting stuck in a local minimum.

This project solves a phrase puzzle. First we define a phrase eg. "EVOLUTIONARY ALGORITHM AT WORK". The algorithm will generate random set of phrases given the size of the phrase, say m also refereed to as the size of the DNA. The fitness function then grades the phrases which are randomly generated by counting the number of correct letters in each phrase. Think of a phrase as part of the population. We can decide on the number of the population to be n. The algorithm then selects the best phrases (Elitism) and uses them to create new phrases using a crossover function. This function takes two good phrases and generates two child phrases that may be better than their parent phrases. The implementation also uses a mutation function in case the population gets stuck on a local minimum. The new phrases are better than the old ones. The process is repeated until we get a solution that is good enough. The algorithm is implemented in C++.

Generate DNA of a phrase

// generate random DNA                            
void DNA::Generate() {
        // Usable characters are simply members of the alphabet including space
	TArray(char) UsableChars = GenerateUsableCharacters();
	for (int i = 0; i < NUM_CHARACTERS; i++) {
		AddCharToGeneratedPhrase(UsableChars[FMath::RandRange(0, UsableChars.Num() - 1)]);
	}
}

Crossover and Mutation

DNA DNA::Crossover(DNA OtherDNA) {
	DNA RetVal = DNA(false);

	const int MinVal = 3;
	const int MidIndex = FMath::RandRange(MinVal, NUM_CHARACTERS - MinVal);
	const int CrossoverSize = NUM_CHARACTERS - MidIndex;

	for (int i = 0; i < NUM_CHARACTERS; i++) {
		if (i < CrossoverSize) {
			ensureAlways(M_GeneratedPhrase.Len() > 0);
			RetVal.AddCharToGeneratedPhrase(M_GeneratedPhrase.GetCharArray()[i]);
		}
		else {
			ensureAlways(OtherDNA.M_GeneratedPhrase.Len() > 0);
			RetVal.AddCharToGeneratedPhrase(OtherDNA.M_GeneratedPhrase.GetCharArray()[i]);
		}
	}

	return RetVal;
}

void DNA::Mutation() {
	TArray(char) UsableChars = GenerateUsableCharacters();

	for (int i = 0; i < M_GeneratedPhrase.Len(); i++) {
		if (FMath::RandRange(0.0f, 1.0f) < MUTATION_CHAR_CHANCE) {
			ensureAlways(M_GeneratedPhrase.Len() > 0);
			M_GeneratedPhrase.GetCharArray()[i] = UsableChars[FMath::RandRange(0, UsableChars.Num() - 1)];
		}
	}
}

Calculate Fitness

int DNA::CalculateAndStoreFitness() {
	int RetVal = 0;

	if (M_StoredFitness == -1) {
		M_StoredFitness = 0; //first time calculating fitness

		for (int i = 0; i < M_GeneratedPhrase.Len(); i++) {
			if (M_GeneratedPhrase.GetCharArray()[i] == TARGET_PHRASE[i]) {
				RetVal++;
			}
		} 
		M_StoredFitness = RetVal; //stored fitness for next time
	}
	else {
		RetVal = M_StoredFitness; //already calculated before, use the stored value
	}
	return RetVal;
}